package com.sicheng.lc.周赛.分类.哈西表or计数or滑动窗口or双指针.双指针;

import java.util.Arrays;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/12 10:45
 */
public class 坐上公交的最晚时间 {
    //https://leetcode.cn/problems/the-latest-time-to-catch-a-bus/


    // 大致思路
    // 找到最后一个可以上车的人，他前面的人全部上车
    // 车未满直接最后一辆车发车时上
    // 满了，从最后一个上车的人开始往前找前，插队到第一个空闲的位置
    public int latestTimeCatchTheBus(int[] buses, int[] passengers, int capacity) {
        Arrays.sort(buses);
        Arrays.sort(passengers);
        int j = 0, i = 0, c = 0;
        for (; i < buses.length; i++) {
            c = capacity;
            // 模拟上车过程, 第i辆车的容量足够 第j位乘客上， j的到站时间小于等于发车时间
            for (; c > 0 && j < passengers.length && passengers[j] <= buses[i]; j++) {
                c--;
            }
        }

        // 最后一个上车的人的索引
        j--;

        int res = c > 0 ? buses[buses.length - 1] : passengers[j];
        while (j >= 0 && res == passengers[j]) {
            j--;
            res--;
        }

        return res;
    }
}
